package 比较排序;

public class QuickSort {
    public static void sort(int[] arr,int left,int right){
        if(left<right){
            int index=getIndex(arr,left,right);
            sort(arr,left,index-1);
            sort(arr,index+1,right);
        }
    }

    public static int getIndex(int[] a,int left,int right){
        int pivot=a[left];//选定主元，默认为最左边
        while (left<right){
            //不断移动右指针直到小于主元
            while (left<right && a[right]>=pivot) right--;
            a[left]=a[right];
            while (left<right && a[left]<=pivot) left++;
            a[right]=a[left];
        }
        a[left]=pivot;
        return left;
    }
}
